class Solution:
    def twoSum(self, nums, target):
        """
        Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target
        You may assume that each input would have exactly one solution, and you may not use the same element twice.
        You can return the answer in any order.

        给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 target的那两个整数，并返回它们的数组下标。
        你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
        你可以按任意顺序返回答案。
        """
        """
        一般解法为两层循环,for(int i=0; i<length-1; i++) for(int j=i+1; j<length; j++)，时间复杂度为O(n²)
        
        快速方法为利用哈希表的快速查找来进行第二元素的查找，因为只遍历一次数组，因此时间复杂度为O(n)
        """
        hashtable = dict() # 创建一个hashTable
        for i, num in enumerate(nums): # 遍历数组种每个元素
            if target - num in hashtable: 
                # 假设nums中存在两个目标数，在hashTable中寻找第二个目标数，若没有则存在表中
                # 举例: nums = [1, 2, 3, 4], target = 4
                # 过程: i = 0, nums[i] = 1, hashTable = {} ===> hashTable = {1: 0}
                # 过程: i = 1, nums[i] = 2, hashTable = {1: 0} ===> hashTable = {1: 0, 2: 1}
                # 过程: i = 2, nums[i] = 3, hashTable = {1: 0, 2: 1} 当 4-1=3在表中被找到，直接返回结果
                # 整个过程只需要遍历一次nums数组，时间复杂度为O(n), 空间复杂度为O(n)，哈希表的存储
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []
    


